package summer.greedy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Solution763 {
    public List<Integer> partitionLabels(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), i);
        }
        int start = 0;
        int cover = 0;
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            int cur = map.get(s.charAt(i));
            if (cur > cover) {
                cover = cur;
            }
            if (i == cover) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}
